|
|
Workshop Report
Colloquium on Implementation of Constraint Logic Programming Systems
URL: http://clip.dia.fi.upm.es/Conferences/CICLOPS-2008/ CICLOPS-es were always succesfull, and CICLOPS2008 was no exception: with about 20 participants, even when colliding with two parallel events, that's clear. The atmosphere was friendly, cooperative and inquisitive: many of us know each other since long, and we appreciate each others work, but we surely remain critical when our peers make bold statements. CICLOPS08 had a 6 presentations on 12 December, and 6 on 13 December. This years workshop was dominated by Paul Tarau who made three contributions. His first presentation showed how a small set of primitives for interaction between two or more very lean Prolog engines can define virtually any complicated built-in predicate, and possibly even tabling: the latter has been an old dream of Paul, and maybe in one of the following CICLOPS-es, we will see that dream come through. His two other talks were related by ranking-unranking bijections - whose practical use still needs to be proven - but the potential is clearly there, e.g. for compressing data structures. In his usual and highly appreciated style, Paul wrapped his ideas as a present to the audience in a foil of historical remarks and he touched in passing almost every important aspect of computer science. Paul also showed himself the unbeatable master at circumventing direct questions. Paolo Moura talked about how to make meta-predicates more secure: he defines a set of syntactical restrictions on programs, so that compliant programs are guaranteed not to abuse the module system through higher-order predicates. One of his restrictions was highly critizised, but that will certainly not stop Paolo to work further in this area: it is clearly a win for Prolog if he can work out a proposal that is accepted widely and makes the language more secure. In all fairness: not every participant was convinced that this is needed. And the old schisma between predicate based and atom based module systems reared its head. Ricardo Rocha gave two talks: one about using a common global trie for storing goals and answers in YapTab. This can reduce the memory requirements considerably, and can speed up programs. It seems to need some more work, but it looks promising. I liked the implied garbage collections issues that this technique raises. His second talk was about optimizing tabled calls to deterministic predicates. Read "deterministic" as "having only one clause", and include extensions like: "activating the last clause of the ones selected by indexing". It is a pity that it only works with batched evaluation, but for someone who wants to implement tabling from scratch, this work also shows how one can save on implementation effort! Pablo Chico de Guzman talked about how a continuation based source to source transformation of a tabled program implements a reasonably efficient tabling mechanisme, ala SLG, while requiring less work in the guts of the Prolog engine. He made a nice comparison with CHAT - one of my favourites of course :-) What CIAO people (and formely together with people from Porto) have achieved is quite amazing because it might give us a more portable way to implement tabling in a new system. Still, depending on the system, one might want to reconsider some decisions so that one does not need to perform surgery in the memory management of the basic engine. At the end of the first half day of CICLOPS, Terrance Swift presented an overview of the efforts of the XSB team - and I guess actually mostly his efforts - to get multi-threaded tabling in XSB going. It was particularly nice that he started from explaining the objectives. And than followed a detailed status report of what was considered finished, almost done, in progress and to be done. To me, it sounded all mind-dazzling: multi-threading and tabling are both on their own very complicated things, and tabling has quite a few variants (scheduling strategies, variant or subsumption based, ...), so combining them is heroic. It seems that teh XSB system is nearly complete in multi-threaded tabling. On Saturday, besides two of the Paul talks mentioned before, we got a talk by Jan Wielemaker who showed how processing a large file is possible without the need to have it all in memory, by using an open ended list whose elements are the characters from the file, and the open end is an attributed variable in which on demand more data is read. To make this work, SWI-Prolog needed to introduce more precise marking during the garbage collection. That is now done by code-scanning from a point where garbage collection can happen. As a novelty, also alternative clauses are scanned for detecting whether a variable from the call is used in any alternative. A set of test programs show how several things can get wrong in different systems. As garbage collection is one of my favourite pass times, I am still intrigued by some test program I did not understand during the presentation, and for sure, I will ask Jan and Ulrich when I have time. Peter Stuckey showed that there is a way to let threads steal work from the search tree of a CSP, based on a dynamically varying confidence that expresses (roughly) how likely it is that a solution will (soon) be found in a particular branch. It is clear that we are talking heuristics here, but as the author might say "hey, if it works, who cares". And indeed it works. A little caution is however in place when superlinear speedups are observed: by parallellizing and applying a work stealing heuristic, the search algorithm itself is changed ! Then again, if it results in nice speedups, who cares. Well, we do care to understand these things of course. Tom Schrijvers talked about an efficient term representation for ground terms in CHR: it is weird that ground terms are worse for indexing than free variables, isn't it ? The reason is that these days, free variables are not as free as before: they can have all sorts of things attached to them - for instance a list of corresponding constraints - because they can have attributes. But ground terms cannot have attributes. The method Tom explained consists in giving ground terms two representations: one as the usual Prolog term, and one as a tuple with both the Prolog term and attributes that make up the needed indexes. The latter is only used when CHR is running. Of course, on the border between Prolog and CHR, one needs to transform the representation. Throw in some optimizations, and nice speedups for some benchmarks follow. I myself had volunteered to give the final talk, and I can only say that the audience was very gentle with me. Above you have seen my personal appreciation of the talks, and you better check for yourself whether I was talking rubbish: have a look in the proceedings at We had also a Session on the Future of CICLOPS: it's not in the proceedings. The participants decided not to change anything to the format, so it must be that everyone is happy. Paul Tarau volunteered to set the next CICLOPS (during ICLP09) in motion at the next call for workshop proposals. It was great as usual, thanks to the efforts Agostino Dovier, the PC committee, the authors of the papers, and the participants: see you next year. |
